package com.gxc.linkedList;

/**
 * 将单链表按某值划分成左边小，中间相等，右边大的形式
 */
public class ListPartition {

    /**
     * 划分为三个链表
     * 左边小的链表
     * 中间相等的链表
     * 右边大的链表
     * 三个链表合并
     * @param head
     * @param pivot
     * @return
     */
    public ListNode handle(ListNode head, int pivot) {
        if (head == null || head.next == null) return head;

        ListNode left = new ListNode(-1);
        ListNode leftH = left;
        ListNode mid = new ListNode(-1);
        ListNode midH = left;
        ListNode right = new ListNode(-1);
        ListNode righH = left;
        ListNode node = null;
        while (head != null) {
            if (head.val == pivot) {
                mid.next = head;
                mid = mid.next;
            } else if (head.val < pivot) {
                left.next = head;
                left = left.next;
            } else {
                right.next = head;
                right = right.next;
            }
            head = head.next;
        }
        left.next = midH.next;
        mid.next = righH.next;
        if (leftH.next == null) {
            leftH.next = midH.next == null ?righH.next:midH.next;
        }
        return leftH.next;
    }

    //第二种　进阶的方法　不需要额外的空间复杂度，且能达到稳定性
    static Node partitionList_2(Node head,int piovt){
        if(head == null)return null;
        Node sH = null,sT = null; //小于部分链表的  head 和tail
        Node eH = null,eT = null; //等于部分链表的　head 和tail
        Node bH = null,bT = null; //大于部分链表的　head 和tail

        Node next = null;  //用来保存下一个结点

        //划分到　三个不同的链表
        while(head != null){
            next = head.next;
            head.next = null; //这个是为了链表拼接后　最后一个就不用再去赋值其next域为null 了
            if(head.value < piovt){  //向　small 部分　分布
                if(sH == null){ //small部分的第一个结点
                    sH = head;
                    sT = head;
                }else {
                    sT.next = head; //把head放到small最后一个
                    sT = head;  //更新small部分的sT
                }
            }else if(head.value == piovt){
                if(eH == null){
                    eH = head;
                    eT = head;
                }else{
                    eT.next = head;
                    eT = head;
                }
            }else {
                if(bH == null){
                    bH = head;
                    bT = head;
                }else {
                    bT.next = head;
                    bT = head;
                }
            }
            head = next;
        }

        //将三个链表合并(注意边界的判断)

        if(null != sT) { //合并small和equal部分
            sT.next = eH;
            eT = eT == null ? sT : eT;
        }
        if(null != eT){
            eT.next = bH;
        }

        return sH != null ? sH : eH != null ? eH : bH;
    }



    public static class ListNode {
        int val;
        ListPartition.ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListPartition.ListNode next) { this.val = val; this.next = next; }
    }
}
